package DataModel.SegmentTree;

import java.util.Hashtable;
import java.util.Stack;
/**
 * Implementation of segment tree postorder iterator
 * @author Guy
 *
 */
public class SegmentTreePostorderIterator implements SegmentTreeIterator {
	private Hashtable<SegmentTreeNode,Boolean> visited = null;
	private Stack<SegmentTreeNode> s = null;
	
	/**
	 * Creates the iterator
	 * @param t - segment tree on which to iterate
	 * @return iterator
	 */
    public static SegmentTreePostorderIterator IteratorInitialize(SegmentTree t) {
		if (t.getRoot()==null) {
			System.err.println("Tree not initialized");
			return null;
		}
		return new SegmentTreePostorderIterator(t.getRoot());
	}
    /**
	 * Creates iterator which will start from specific node
	 * @param n start node
	 * @return iterator
	 */
	public static SegmentTreePostorderIterator IteratorInitialize(SegmentTreeNode n) {
		if (n ==null) {
			System.err.println("Tree not initialized");
			return null;

		}
		return new SegmentTreePostorderIterator(n); 
	}
	
	public SegmentTreePostorderIterator(SegmentTreeNode start) {
		this.s = new Stack<SegmentTreeNode>();
		this.visited = new Hashtable<SegmentTreeNode, Boolean>();

		s.push(start);
		
	}
	
	/**
	 * Returns true if unvisited node exists
	 */
	
	public boolean hasNext() {
		return !s.isEmpty();
	}

	/**
	 * Next tree node pointed by iterator
	 * @return next tree node
	 */
	public SegmentTreeNode next() {
		if (s.isEmpty()) return null;
		SegmentTreeNode res = null;
		while (!s.isEmpty()) {
			SegmentTreeNode t = s.peek();
			if (visited.containsKey(t)) {
				//visit t
				res = t;
				s.pop();
				break;
			} else {
				visited.put(t, true);
				if (t.rightSon() != null ) {
					s.push(t.rightSon());
					
				}
				if (t.leftSon()  != null ) {
					s.push(t.leftSon());
				}
			}
		}
		return res;
	}

}
